package com.shuzijun.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;

public class TwoSum{
    public static void main(String[] args) {
         Solution solution = new TwoSum().new Solution();
         solution.twoSum(new int[]{3,2,4},6);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

        public int[] twoSum(int[] nums, int target) {
            int n = nums.length;
            int[] sortedNums = new int[n];
            for (int i = 0; i < n; i++) {
                sortedNums[i] = nums[i];
            }

            Arrays.sort(sortedNums);
            boolean[] used = new boolean[n];
            int p = 0;
            int q = n-1;
            while (p < q){
                int sum = sortedNums[p] + sortedNums[q];
                if (sum == target){
                    int oldp = find(nums,used,sortedNums[p]);
                    int oldq = find(nums,used,sortedNums[q]);
                    return new int[]{oldp,oldq};
                } else if (sum < target) {
                    p++;
                }else {
                    q--;
                }
            }
            return new int[0];
        }

        private int find(int[] nums, boolean[] used, int value) {
            int i = 0;
            while (i < nums.length){
                if (nums[i] == value && used[i] == false){
                    used[i] = true;
                    break;
                }
                i++;
            }
            return i;
        }
//        public int[] twoSum(int[] nums, int target) {
//            int n = nums.length;
//            int[] sortedNums = new int[n];
//            for (int i = 0; i < n; i++) {
//                sortedNums[i] = nums[i];
//            }
//            Arrays.sort(sortedNums);
//            boolean[] used = new boolean[n];
//            int p = 0;
//            int q = n-1;
//            while (p < q){
//                int sum = sortedNums[p] + sortedNums[q];
//                if (sum == target){
//                    int oldp = find(nums,used,sortedNums[p]);
//                    int oldq = find(nums,used,sortedNums[q]);
//                    return new int[]{oldp,oldq};
//                } else if (sum < target) {
//                    p++;
//                }else {
//                    q--;
//                }
//            }
//            return new int[0];
//        }
//
//        private int find(int[] nums, boolean[] used, int value) {
//            int i = 0;
//            while (i < nums.length){
//                if (nums[i] == value && used[i] == false){
//                    used[i] = true;
//                    break;
//                }
//                i++;
//            }
//            return i;
//        }

//        public int[] twoSum(int[] nums, int target) {
//            for (int i = 0; i < nums.length; i++) {
//                for (int j = i+1; j < nums.length; j++) {
//                    if (nums[i] + nums[j] == target){
//                        return new int[]{i,j};
//                    }
//                }
//            }
//            return null;
//        }

//        public int[] twoSum(int[] nums, int target) {
//            int n = nums.length;
//
//            int[] sortNums = new int[n];
//            for (int i = 0; i < n; i++) {
//                sortNums[i] = nums[i];
//            }
//            boolean[] used = new boolean[n];
//            Arrays.sort(sortNums);
//
//            int i = 0;
//            int j = n-1;
//            while (i < j){
//                int sum = sortNums[i] + sortNums[j];
//                if ( sum == target){
//                    int oldp = finds(nums,used,sortNums[i]);
//                    int oldq = finds(nums,used,sortNums[j]);
//                    return new int[]{oldp,oldq};
//                } else if (sum < target) {
//                    i++;
//                }else {
//                    j--;
//                }
//            }
//
//           return new  int[0];
//        }
//
//        private int finds(int[] nums, boolean[] used, int value) {
//            int i = 0;
//            while (i < nums.length){
//                if (nums[i] == value && used[i] == false){
//                    used[i] = true;
//                    break;
//                }
//                i++;
//            }
//            return i;
//        }


//        public int[] twoSum(int[] nums, int target) {
//            int n = nums.length;
//            HashMap<Integer, Integer> map = new HashMap<>();
//            for (int i = 0; i < n; i++) {
//                map.put(nums[i],i);
//            }
//            for (int i = 0; i < n; i++) {
//                                if (map.containsKey(target - nums[i])){
//                    int value = map.get(target - nums[i]);
//                    if (value != i){
//                        return new int[]{i,value};
//                    }
//                }
//            }
//
//            return new int[0];
//        }












//    public int[] twoSum(int[] nums, int target) {
//        int n = nums.length;
//        HashMap<Integer, Integer> hashMap = new HashMap<>();
//        for (int i = 0; i < n; i++) {
//            hashMap.put(nums[i], i);
//        }
//
//        for (int i = 0; i < n; i++) {
//            if (hashMap.containsKey(target - nums[i])){
//                Integer value = hashMap.get(target - nums[i]);
//                if (value != i){
//                    return new int[]{i,value};
//                }
//            }
//        }
//        return new int[0];
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

}